iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0

今日題目

題目連結:100. same tree
題目主題:Tree, Depth-First Search, Breadth-First Search, Binary Tree

在練習過Preorder、Inorder、Postorder三種Traversal以後,今天找了一題最後再來練習一下Depth-First Search主題。


簡單說說 Tree Visualizer

雖然在前幾篇都練習過如何把一個陣列看成一棵樹,但這邊可以分享一下,如果今天懶得自己想像Tree的樣子,可以用Leetcode提供的功能來顯示。

https://ithelp.ithome.com.tw/upload/images/20210927/201413369Eejg77rOf.png

如上圖,可以在Testcase的地方,開啟Tree Visualizer,這時候上面就會出現一棵樹的形狀,下方的框框也會有藍色的一條做標示,告訴你現在這棵樹是用哪個陣列形成的。


題目解說

建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。

題目會給兩棵樹,分別為 p 及 q,目標是檢查這兩棵樹是否所有TreeNode都是一樣的,若都是一樣的回傳True,若不一樣就回傳False。

約束:

  • 樹的節點總數範圍在 [0, 100]
  • -10的4次方 <= Node.val <= 10的4次方

範例1

輸入: p = [1,2,3], q = [1,2,3]
輸出: true

範例2

輸入: p = [1,2], q = [1,null,2]
輸出: false

範例3

輸入: p = [1,2,1], q = [1,1,2]
輸出: false

建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。


解題的想像

文字描述

  1. 寫一個遞迴方法,這個方法會傳兩棵樹目前要前往的TreeNode。
  2. 每次呼叫這個方法,前往的節點兩邊會是同步的。
  3. 用Preorder的方式,每進入一個節點直接檢查當下節點是否為相同,檢查的狀態有以下:
    • 目前節點都為空,代表目前都相同,繼續檢查下一個節點
    • 目前節點一個為空、一個不為空,代表兩棵樹已經不同了
    • 目前節點都有值,但值不相同,代表兩棵樹已經不同了
  4. 全部節點都走完,並且過程中都沒有出現不同的節點,代表最終兩棵樹是相同長相的樹。

圖解過程

範例: p = [1,2,3], q = [1,2,3]

https://ithelp.ithome.com.tw/upload/images/20210927/20141336lKKHPpT22a.png

如上圖,檢查兩棵樹是否一樣,這次是用Preorder Traversal來實作,也就是進入一個節點就檢查,可以看到step1 ~ step4 基本上都是,兩邊的樹 p 跟 q 都是同時在前進的,過程中每一步都會去確認目前兩顆樹的節點是否相同,即便是綠色圓這個路徑的每一步都會確認是否相同,一直到整棵樹都走過一次沒有不一樣,最終就是回傳True。

若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。


程式碼撰寫

class Solution:
    def sameNode(self, p: TreeNode, q: TreeNode):
        # 目前節點都為空
        if p == None and q == None:
            return True
        # 檢查 兩種狀況都代表樹長的不同
        # 1. 目前節點是否一個為空、一個不為空
        # 2. 兩個都有節點但值不一樣
        if ((p != None and q == None)
         or (p == None and q != None)
         or (p.val != q.val)):
            return False
        # 若已經檢查到有一個節點不相同,直接結束這個遞迴
        if not self.sameNode(p.left, q.left):
            return False
        # 若已經檢查到有一個節點不相同,直接結束這個遞迴
        if not self.sameNode(p.right, q.right):
            return False
        # 節點都相同才會走到這
        return True
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return self.sameNode(p, q)

希望您今天能瞭解到...

  1. Tree Visualizer 的用法
  2. 100.same tree 的解題方法

若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~

Next:965. Univalued Binary Tree


上一篇
Day 12:145. Binary Tree Postorder Traversal
下一篇
Day 14:965. Univalued Binary Tree
系列文
我在刷LeetCode時邂逅了Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言